#pragma once
#include <iostream>
#include <vector>
#include <time.h>
#include <random>
#include <chrono>

using namespace std;

struct SkipListNode
{
    vector<SkipListNode *> _nextV;
    size_t _val;

    SkipListNode(int val, int level)
        : _val(val), _nextV(level, nullptr)
    {
    }
};

class SkipList
{
    typedef SkipListNode Node;

public:
    SkipList()
    {
        srand(time(0));

        // 头节点，层数是1
        _head = new Node(-1, 1);
    }
    bool search(int target)
    {
        Node *cur = _head;
        size_t level = cur->_nextV.size() - 1;

        while (level >= 0)
        {
            // 目标值比下一个节点大，要向右走
            if (cur->_nextV[level] && cur->_nextV[level]->_val < target)
            {
                cur = cur->_nextV[level];
            }
            // 目标值的下一个节点为空或者目标值小于下一个节点，向下走
            else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target)
            {
                level--;
            }
            else
            {
                return true;
            }
        }

        return false;
    }

    vector<Node *> FindPrevNode(int num)
    {
        Node *cur = _head;
        int level = _head->_nextV.size() - 1;

        // 插入位置每一层前一个节点指针
        vector<Node *> prevV(level + 1, _head);
        while (level >= 0)
        {
            // 目标值比下一个节点大，要向右走
            if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
            {
                cur = cur->_nextV[level];
            }
            // 目标值的下一个节点为空或者目标值小于下一个节点，向下走
            else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val >= num)
            {
                // 更新level层前一个
                prevV[level] = cur;
                level--;
            }
        }

        return prevV;
    }

    int RandomLevel()
    {
        // int level = 1;
        // if (rand() > _p * RAND_MAX && level < maxlevel)
        // {
        //     level++;
        // }

        // return level;

        static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());
        static std::uniform_real_distribution<double> distribution(0.0, 1.0);

        size_t level = 1;
        while (distribution(generator) <= _p && level < _maxlevel)
        {
            ++level;
        }

        return level;
    }
    bool erase(int num)
    {
        vector<Node *> prevV = FindPrevNode(num);
        // 第一层的下一个为nullptr或者不为num
        if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)
        {
            return false;
        }
        else
        {
            Node *del = prevV[0]->_nextV[0];
            // del节点的前后节点的每一层指针链接起来
            for (int i = 0; i < del->_nextV.size(); i++)
            {
                prevV[i]->_nextV[i] = del->_nextV[i];
            }
            delete del;

            // 如果删除的是最高层，就降低头结点的层数
            int i = _head->_nextV.size() - 1;
            while (i >= 0)
            {
                if (_head->_nextV[i] == nullptr)
                    --i;
                else
                    break;
            }
            _head->_nextV.resize(i + 1);

            return true;
        }
    }
    void add(int num)
    {
        vector<Node *> prevV = FindPrevNode(num);

        int n = RandomLevel();
        Node *newnode = new Node(num, n);

        // 如果n超过当前最大的层数，那就升高一下_head的层数
        if (n > _head->_nextV.size())
        {
            _head->_nextV.resize(n, nullptr);
            prevV.resize(n, _head);
        }

        // 链接前后节点
        for (size_t i = 0; i < n; ++i)
        {
            newnode->_nextV[i] = prevV[i]->_nextV[i];
            prevV[i]->_nextV[i] = newnode;
        }
    }

    void Print()
    {
        Node *cur = _head;
        while (cur)
        {
            // 打印每一个cur节点
            printf("%2ld\n", cur->_val);
            for (auto e : cur->_nextV)
            {
                printf("%2s", "↓");
            }
            printf("\n");

            cur = cur->_nextV[0];
        }
    }

private:
    Node *_head;
    double _p = 0.25;
    size_t _maxlevel = 32;
};

void Test()
{
    SkipList sl;
    int a[] = {5, 2, 3, 8, 9, 6, 11, 7, 12, 15};
    for (auto e : a)
    {
        sl.add(e);
    }
    sl.Print();
    cout << endl;

    int x;
    cin >> x;
    sl.erase(x);
    cout << endl;

    sl.Print();
}